package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/22 9:25
 */
public class C292 {


    public static boolean canWinNim(int n) {
        if(n <= 3) return true;
        return !canWinNim(n-1) || !canWinNim(n-3) || !canWinNim(n-2);
    }

    public static boolean dp(int n) {
        if(n <= 3) return true;
        boolean[] dp = new boolean[n + 1];
        dp[1] = true;   dp[2] = true;    dp[3] = true;
        for (int i = 4; i <= n; i++) {
            dp[i] = !dp[i-1] || !dp[i-2] || !dp[i-3];
        }
        return dp[n];
    }

    // 空间压缩
    public static boolean dp2(int n) {
        if(n <= 3) return true;
        boolean a = true, b = true, c = true;
        boolean d = false;
        for (int i = 4; i <= n; i++) {
            d = !a || !b || !c;
            a =b;   b = c;  c = d;
        }
        return d;
    }

    // 找规律
    public static boolean dp3(int n) {
        return n % 4 != 0;
    }


    public static void main(String[] args) {
        int n = 1199886170;
//        System.out.println(canWinNim(n));
//        System.out.println(dp(n));
//        System.out.println(dp2(n));

        for (int i = 1; i <= 200; i++) {
            System.out.println( i + " :: " + dp2(i));
            System.out.println( i + " :: " + dp3(i));
        }

    }

}
